package leetcode;

public class LC33 {
    public static void main(String[] args) {
        LC33 lc33 = new LC33();
        ListNode.print(lc33.sortList(ListNode.ln(new int[]{4,19,14,5,-3,1,8,5,11,1})));
        ListNode.print(lc33.sortList(ListNode.ln(new int[]{4,2,1,3})));
    }
    public ListNode sortList(ListNode head) {
        ListNode temp = head;
        int i = 0;
        while (temp != null) {
            temp = temp.next;
            i++;
        }
        temp = head;
        ListNode s = head;
        ListNode next = head;
        for (int j = 0; j < i / 2; j++) {
            s = next;
            next = next.next;
        }
        s.next = null;
        return merge(sort(temp,i / 2),sort(next, i - i/2));
    }
    public ListNode sort(ListNode first, int length){
        if (length < 2) return first;
        ListNode y = first;
        ListNode s = first;
        for (int i = 0; i < length / 2; i++) {
            s = y;
            y = y.next;
        }
        s.next = null;
        return merge(sort(first, length / 2), sort(y, length - length / 2));
    }
    public ListNode merge(ListNode a, ListNode b){
        ListNode x = null;
        ListNode y = null;
        while(a != null && b != null){
            if (a.val > b.val){
                if (x == null) x = b;
                else y.next = b;
                y = b;
                b = b.next;
            }else {
                if (x == null) x = a;
                else y.next = a;
                y = a;
                a = a.next;
            }
        }
        if (a == null) a = b;
        y.next = a;
        return x;
    }
}
